<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT. Input Specification: Each input file cont">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="article">
<meta property="og:title" content="PAT A1075">
<meta property="og:url" content="http://www.hemisu.com/2017/02/09/115/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT. Input Specification: Each input file cont">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2017-02-09T22:09:02.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="PAT A1075">
<meta name="twitter:description" content="The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT. Input Specification: Each input file cont">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/2017/02/09/115/">





  <title>PAT A1075 | 何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/09/115/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">PAT A1075</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-09T16:55:11+00:00">
                2017-02-09
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 3 positive integers, N (&lt;=104), the total number of users, K (&lt;=5), the total number of problems, and M (&lt;=105), the total number of submittions. It is then assumed that the user id’s are 5-digit numbers from 00001 to N, and the problem id’s are from 1 to K. The next line contains K positive integers p[i] (i=1, …, K), where p[i] corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submittion in the following format:</p>
<p>user_id problem_id partial_score_obtained</p>
<p>where partial_score_obtained is either -1 if the submittion cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, you are supposed to output the ranklist in the following format:</p>
<p>rank user_id total_score s[1] … s[K]</p>
<p>where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the i-th problem. If a user has never submitted a solution for a problem, then “-“ must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.</p>
<p>The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id’s. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.</p>
<p>Sample Input:<br>7 4 20<br>20 25 25 30<br>00002 2 12<br>00007 4 17<br>00005 1 19<br>00007 2 25<br>00005 1 20<br>00002 2 2<br>00005 1 15<br>00001 1 18<br>00004 3 25<br>00002 2 25<br>00005 3 22<br>00006 4 -1<br>00001 2 18<br>00002 1 20<br>00004 1 15<br>00002 4 18<br>00001 3 4<br>00001 4 2<br>00005 2 -1<br>00004 2 0<br>Sample Output:<br>1 00002 63 20 25 - 18<br>2 00005 42 20 0 22 -<br>2 00007 42 - 25 - 17<br>2 00001 42 18 18 4 2<br>5 00004 40 15 0 25 -</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">struct student&#123;</span><br><span class="line">    int id;</span><br><span class="line">    int score[6];</span><br><span class="line">    bool flag;//是否有能通过编译的提交</span><br><span class="line">    int score_all;</span><br><span class="line">    int solve;//满分题数</span><br><span class="line">&#125;stu[10010];</span><br><span class="line">int full[6];</span><br><span class="line">int n, k ,m;</span><br><span class="line">bool cmp (student a, student b)&#123;</span><br><span class="line">    if (a.score_all != b.score_all) &#123;</span><br><span class="line">        return a.score_all &gt; b.score_all;</span><br><span class="line">    &#125;else if (a.solve != b.solve)&#123;</span><br><span class="line">        return a.solve &gt; b.solve;</span><br><span class="line">    &#125;return a.id &lt; b.id;</span><br><span class="line">&#125;</span><br><span class="line">void init()&#123;</span><br><span class="line">    for (int i = 1; i &lt;=n; i++) &#123;</span><br><span class="line">        stu[i].id = i;</span><br><span class="line">        stu[i].score_all = 0;</span><br><span class="line">        stu[i].solve = 0;</span><br><span class="line">        stu[i].flag = false;</span><br><span class="line">        memset(stu[i].score, -1, sizeof(stu[i].score));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;n, &amp;k, &amp;m);</span><br><span class="line">    init();</span><br><span class="line">    for (int i = 1 ; i &lt;= k ; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;full[i]);//读取分数</span><br><span class="line">    &#125;</span><br><span class="line">    int u_id, p_id, score_obtained;//考生ID，题目ID，所获分值</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d%d&quot;, &amp;u_id, &amp;p_id, &amp;score_obtained);</span><br><span class="line">        if (score_obtained != -1) &#123;</span><br><span class="line">            //通过编译</span><br><span class="line">            stu[u_id].flag = true;</span><br><span class="line">        &#125;</span><br><span class="line">        if (score_obtained == -1 &amp;&amp; stu[u_id].score[p_id] == -1) &#123;</span><br><span class="line">            //某题编译错误，分值记为0，便于输出</span><br><span class="line">            stu[u_id].score[p_id] = 0;</span><br><span class="line">        &#125;</span><br><span class="line">        if (score_obtained == full[p_id] &amp;&amp; stu[u_id].score[p_id] &lt; full[p_id]) &#123;</span><br><span class="line">            //某一题获得了满分</span><br><span class="line">            stu[u_id].solve++;</span><br><span class="line">        &#125;</span><br><span class="line">        if (score_obtained &gt; stu[u_id].score[p_id]) &#123;</span><br><span class="line">            //某题获得了更高的分数</span><br><span class="line">            stu[u_id].score[p_id] = score_obtained;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        for (int j = 1; j &lt;= k; j++) &#123;</span><br><span class="line">            if (stu[i].score[j] != -1) &#123;</span><br><span class="line">                //计算总分</span><br><span class="line">                stu[i].score_all += stu[i].score[j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    sort(stu + 1, stu + n + 1, cmp);</span><br><span class="line">    int r = 1;//当前排名</span><br><span class="line">    for (int i = 1; i &lt;= n &amp;&amp; stu[i].flag == true; i++) &#123;</span><br><span class="line">        if (i &gt; 1 &amp;&amp; stu[i].score_all != stu[i - 1].score_all) &#123;</span><br><span class="line">            r = i;</span><br><span class="line">        &#125;</span><br><span class="line">        printf(&quot;%d %05d %d&quot;, r, stu[i].id, stu[i].score_all );</span><br><span class="line">        for (int j = 1; j &lt;= k; j++) &#123;</span><br><span class="line">            if (stu[i].score[j] == -1) &#123;</span><br><span class="line">                printf(&quot; -&quot;);//没有提交 显示-</span><br><span class="line">            &#125;else&#123;</span><br><span class="line">                printf(&quot; %d&quot;, stu[i].score[j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/02/09/114/" rel="next" title="PAT A1055">
                <i class="fa fa-chevron-left"></i> PAT A1055
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2017/02/09/116/" rel="prev" title="PAT A1083">
                PAT A1083 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
